package com.hy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:累加数，搜集所有符合条件的斐波那契序列
 * author: Mr.Du
 * Date: 2023/10/19
 * Time: 18:57
 */
public class IsAdditiveNumber2 {

    List<List<Long>> res = new ArrayList<>();
    LinkedList<Long> list = new LinkedList<>();
    public List<List<Long>> isAdditiveNumber(String num) {
        dfs(num, 0);
        return res;
    }

    public void dfs(String num, int start){
        if(start == num.length() && list.size() > 2){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = start;i < num.length();i++){
            if(num.charAt(start) == '0' && i > start) break;
            String s = num.substring(start, i + 1);
            int size = list.size();
            long cur = Long.valueOf(s);
            if(s.length() > num.length() / 2) break;
            if(size >= 2){
                if(cur > list.get(size - 1) + list.get(size - 2)) break;
                if(cur < list.get(size - 1) + list.get(size - 2)) continue;
            }
            list.add(cur);
            dfs(num, i + 1);
            list.removeLast();
        }
    }

    public static void main(String[] args) {
        IsAdditiveNumber2 isAdditiveNumber = new IsAdditiveNumber2();
        List<List<Long>> additiveNumber = isAdditiveNumber.isAdditiveNumber("1101111");
        System.out.println(additiveNumber);
    }

}
